{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Substring With Largest Variance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestVariance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大波动的子字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>字符串的 <strong>波动</strong>&nbsp;定义为子字符串中出现次数 <strong>最多</strong>&nbsp;的字符次数与出现次数 <strong>最少</strong>&nbsp;的字符次数之差。</p>\n",
    "\n",
    "<p>给你一个字符串&nbsp;<code>s</code>&nbsp;，它只包含小写英文字母。请你返回 <code>s</code>&nbsp;里所有 <strong>子字符串的</strong>&nbsp;<strong>最大波动</strong>&nbsp;值。</p>\n",
    "\n",
    "<p><strong>子字符串</strong> 是一个字符串的一段连续字符序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"aababbb\"\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>\n",
    "所有可能的波动值和它们对应的子字符串如以下所示：\n",
    "- 波动值为 0 的子字符串：\"a\" ，\"aa\" ，\"ab\" ，\"abab\" ，\"aababb\" ，\"ba\" ，\"b\" ，\"bb\" 和 \"bbb\" 。\n",
    "- 波动值为 1 的子字符串：\"aab\" ，\"aba\" ，\"abb\" ，\"aabab\" ，\"ababb\" ，\"aababbb\" 和 \"bab\" 。\n",
    "- 波动值为 2 的子字符串：\"aaba\" ，\"ababbb\" ，\"abbb\" 和 \"babb\" 。\n",
    "- 波动值为 3 的子字符串 \"babbb\" 。\n",
    "所以，最大可能波动值为 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"abcde\"\n",
    "<b>输出：</b>0\n",
    "<strong>解释：</strong>\n",
    "s 中没有字母出现超过 1 次，所以 s 中每个子字符串的波动值都是 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>s</code>&nbsp; 只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [substring-with-largest-variance](https://leetcode.cn/problems/substring-with-largest-variance/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [substring-with-largest-variance](https://leetcode.cn/problems/substring-with-largest-variance/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aababbb\"', '\"abcde\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "\n",
    "\n",
    "# aa...aab\n",
    "def mode1(n, iter_s, a):\n",
    "    res = n-1\n",
    "    max_res = res\n",
    "    for c in iter_s:\n",
    "        if c == a:\n",
    "            res += 1\n",
    "            max_res = max(res, max_res)\n",
    "        else:\n",
    "            max_res = max(res, max_res)\n",
    "            res -= 1\n",
    "            if res < 0:\n",
    "                return max(max_res, mode2(iter_s, a))\n",
    "    return max_res\n",
    "\n",
    "\n",
    "# b开头\n",
    "def mode2(iter_s, a):\n",
    "    for c in iter_s:\n",
    "        if c == a:\n",
    "            break\n",
    "    else:\n",
    "        return 0\n",
    "    n = 1\n",
    "    for c1 in iter_s:\n",
    "        if c1 == a:\n",
    "            n += 1\n",
    "        else:\n",
    "            return mode1(n, iter_s, a)\n",
    "    return n-1\n",
    "\n",
    "\n",
    "def func1(a, b, iter_s):\n",
    "    c = next(iter_s)\n",
    "    # 等于a mode1\n",
    "    if c == a:\n",
    "        n = 1\n",
    "        for c in iter_s:\n",
    "            # 遇到 aaab 调用mode2,参数为a的个数\n",
    "            if c == b:\n",
    "                return mode1(n, iter_s, a)\n",
    "            n += 1\n",
    "    # 等于b mode 2\n",
    "    elif c == b:\n",
    "        return mode2(iter_s, a)\n",
    "    return 0\n",
    "\n",
    "\n",
    "def func2(a, b, s):\n",
    "    for c in s:\n",
    "        if c in (a, b):\n",
    "            yield c\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for a, b in itertools.permutations(set(s), 2):\n",
    "            iter_s = func2(a, b, s)\n",
    "            res = max(res, func1(a, b, iter_s))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        key = Counter(s).keys()\n",
    "        ans = 0\n",
    "        for high_ch in key:\n",
    "            for low_ch in key:\n",
    "                if high_ch != low_ch:\n",
    "                    f, g = 0, float(\"-inf\")\n",
    "                    for index in range(len(s)):\n",
    "                        if s[index] == high_ch:\n",
    "                            f, g = max(f, 0) + 1, g + 1\n",
    "                        elif s[index] == low_ch:\n",
    "                            f, g = max(f, 0) - 1, max(f, g, 0) - 1\n",
    "                        else:\n",
    "                            continue\n",
    "                        ans = max(ans, g)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for a, b in itertools.permutations(set(s), 2):\n",
    "            diff, diff_with_b = 0, -inf\n",
    "            for ch in s:\n",
    "                if ch == a:\n",
    "                    diff += 1\n",
    "                    diff_with_b += 1\n",
    "                    ans = max(ans, diff_with_b)\n",
    "                elif ch == b:\n",
    "                    diff_with_b = diff-1  # 记录包含 b 时的 diff\n",
    "                    diff = max(0, diff_with_b)\n",
    "                    ans = max(ans, diff_with_b)\n",
    "                else:\n",
    "                    continue\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "\n",
    "\n",
    "# aa...aab\n",
    "def mode1(n, iter_s, a):\n",
    "    res = n-1\n",
    "    max_res = res\n",
    "    for c in iter_s:\n",
    "        if c == a:\n",
    "            res += 1\n",
    "            max_res = max(res, max_res)\n",
    "        else:\n",
    "            # max_res = max(res, max_res)\n",
    "            res -= 1\n",
    "            if res < 0:\n",
    "                return max(max_res, mode2(iter_s, a))\n",
    "    return max_res\n",
    "\n",
    "\n",
    "# b开头\n",
    "def mode2(iter_s, a):\n",
    "    for c in iter_s:\n",
    "        if c == a:\n",
    "            break\n",
    "    else:\n",
    "        return 0\n",
    "    n = 1\n",
    "    for c1 in iter_s:\n",
    "        if c1 == a:\n",
    "            n += 1\n",
    "        else:\n",
    "            return mode1(n, iter_s, a)\n",
    "    return n-1\n",
    "\n",
    "\n",
    "def func1(a, b, iter_s):\n",
    "    c = next(iter_s)\n",
    "    # 等于a mode1\n",
    "    if c == a:\n",
    "        n = 1\n",
    "        for c in iter_s:\n",
    "            # 遇到 aaab 调用mode2,参数为a的个数\n",
    "            if c == b:\n",
    "                return mode1(n, iter_s, a)\n",
    "            n += 1\n",
    "    # 等于b mode 2\n",
    "    elif c == b:\n",
    "        return mode2(iter_s, a)\n",
    "    return 0\n",
    "\n",
    "\n",
    "def func2(a, b, s):\n",
    "    for c in s:\n",
    "        if c in (a, b):\n",
    "            yield c\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for a, b in itertools.permutations(set(s), 2):\n",
    "            iter_s = func2(a, b, s)\n",
    "            res = max(res, func1(a, b, iter_s))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for a, b in permutations(ascii_lowercase, 2):\n",
    "            diff, diff_with_b = 0, -inf\n",
    "            for ch in s:\n",
    "                if ch == a:\n",
    "                    diff += 1\n",
    "                    diff_with_b += 1\n",
    "                elif ch == b:\n",
    "                    diff -= 1\n",
    "                    diff_with_b = diff  # 记录包含 b 时的 diff\n",
    "                    diff=max(0,diff)\n",
    "                if diff_with_b > ans:\n",
    "                    ans = diff_with_b\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        for a, b in permutations(ascii_lowercase, 2):\n",
    "            diff = 0\n",
    "            i = 0\n",
    "            while i < n and (ch := s[i]) != b:\n",
    "                if ch == a:\n",
    "                    diff += 1\n",
    "                i += 1\n",
    "            if i == n:\n",
    "                continue\n",
    "            assert s[i] == b\n",
    "\n",
    "            while i < n:\n",
    "                assert s[i] == b\n",
    "                i += 1\n",
    "                if diff == 0:\n",
    "                    while i < n:\n",
    "                        if (ch := s[i]) == b:\n",
    "                            if diff > 0:\n",
    "                                break\n",
    "                        elif ch == a:\n",
    "                            diff += 1\n",
    "                        i += 1\n",
    "                    i += 1\n",
    "                diff -= 1\n",
    "                while i < n:\n",
    "                    if (ch := s[i]) == b:\n",
    "                        if diff == 0:\n",
    "                            break\n",
    "                        ans = max(ans, diff)\n",
    "                        diff -= 1\n",
    "                    elif ch == a:\n",
    "                        diff += 1\n",
    "                    i += 1\n",
    "                ans = max(ans, diff)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def func(self, s, a, b):\n",
    "        # 遍历 s 中的每个字符\n",
    "        for c in s:\n",
    "            # 如果字符是 a 或 b 中的一个，则 yield 返回它\n",
    "            if c in (a, b):\n",
    "                yield c\n",
    "\n",
    "    def largestVariance(self, s):\n",
    "        res = 0\n",
    "        # 生成 s 中两个不同字符的所有排列\n",
    "        for a, b in permutations(set(s), 2):\n",
    "            # 生成一个迭代器 iters\n",
    "            iters = self.func(s, a, b)\n",
    "            # 调用 func1 方法返回最大值，并更新 res\n",
    "            res = max(res, self.func1(iters, a, b))\n",
    "        return res\n",
    "\n",
    "    def func1(self, iters, a, b):  # a 是较大的字符，b 是较小的字符\n",
    "        # 从 iters 中获取下一个字符 c\n",
    "        c = next(iters)\n",
    "        # 如果 c 等于 a\n",
    "        if c == a:\n",
    "            n = 1\n",
    "            # 统计字符 a 的个数，并根据一定规则返回最大值\n",
    "            for ch in iters:\n",
    "                if ch == b:\n",
    "                    return self.mode1(n, iters, a)\n",
    "                n += 1\n",
    "        else:\n",
    "            # 如果 c 不等于 a，则调用 mode2 方法\n",
    "            return self.mode2(iters, a)\n",
    "        return 0\n",
    "\n",
    "    def mode1(self, n, iters, a):\n",
    "        res = n - 1\n",
    "        tep = res\n",
    "        # 统计字符 a 的个数，并根据一定规则返回最大值\n",
    "        for ch in iters:\n",
    "            if ch == a:\n",
    "                tep += 1\n",
    "                res = max(res, tep)\n",
    "                continue\n",
    "            if tep == 0:\n",
    "                return self.mode2(iters, a)\n",
    "            tep -= 1\n",
    "        return res\n",
    "\n",
    "    def mode2(self, iters, a):\n",
    "        # 从 iters 中查找字符 a\n",
    "        for v in iters:\n",
    "            if v == a:\n",
    "                break\n",
    "        else:\n",
    "            return 0\n",
    "        n = 1\n",
    "        # 统计字符 a 的个数，并根据一定规则返回最大值\n",
    "        for ch in iters:\n",
    "            if ch == a:\n",
    "                n += 1\n",
    "                continue\n",
    "            return self.mode1(n, iters, a)\n",
    "        return n - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for a, b in permutations(ascii_lowercase, 2):\n",
    "            diff = 0\n",
    "            flg = -2\n",
    "            for ch in s:\n",
    "                if ch == a:\n",
    "                    diff += 1\n",
    "                    if flg != -2:\n",
    "                        ans = max(ans, diff - flg)\n",
    "                elif ch == b:\n",
    "                    flg = diff - 1 < 0\n",
    "                    diff = max(diff-1, 0)\n",
    "                    ans = max(ans,diff)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import permutations\n",
    "def func2(s1,s2,s):\n",
    "    for ss in s:\n",
    "        if ss in (s1,s2):\n",
    "            yield ss\n",
    "def mode1(s1,sum_s1,iter_s):\n",
    "    res = sum_s1-1\n",
    "    res1 = res\n",
    "    for s in iter_s:\n",
    "        if s == s1:\n",
    "            res1 += 1\n",
    "            res = max(res,res1)\n",
    "        else:\n",
    "            if res1 == 0:\n",
    "                return mode2(s1,iter_s)\n",
    "            res1 -= 1\n",
    "    return res\n",
    "def mode2(s1,iter_s):\n",
    "    for s in iter_s:\n",
    "        if s == s1:\n",
    "            break\n",
    "    else:\n",
    "        return 0\n",
    "    sum_s1 = 1\n",
    "    for ss in iter_s:\n",
    "        if ss != s1:\n",
    "            return mode1(s1,sum_s1,iter_s)\n",
    "        sum_s1 += 1\n",
    "    return sum_s1-1\n",
    "\n",
    "\n",
    "\n",
    "def func1(s1,s2,iter_s):\n",
    "    c = next(iter_s)\n",
    "    if c == s1:\n",
    "        sum_s1 = 1\n",
    "        for s in iter_s:\n",
    "            if s == s2:\n",
    "                return mode1(s1,sum_s1,iter_s)\n",
    "            sum_s1 += 1\n",
    "    else:\n",
    "        return mode2(s1,iter_s)\n",
    "    return 0\n",
    "class Solution:\n",
    "    \n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for s1,s2 in permutations(set(s),2):\n",
    "            iter_s = func2(s1,s2,s)\n",
    "            ans = max(ans,func1(s1,s2,iter_s))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        if s.count(s[0]) == len(s):\n",
    "            return 0\n",
    "        ans = 0\n",
    "        diff = [[0] * 26 for _ in range(26)]\n",
    "        diff_with_b = [[-inf] * 26 for _ in range(26)]\n",
    "        for ch in s:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            for i in range(26):\n",
    "                if i == ch:\n",
    "                    continue\n",
    "                diff[ch][i] += 1  # a=ch, b=i\n",
    "                diff_with_b[ch][i] += 1\n",
    "                diff[i][ch] -= 1  # a=i, b=ch\n",
    "                diff_with_b[i][ch] = diff[i][ch]\n",
    "                if diff[i][ch] < 0:\n",
    "                    diff[i][ch] = 0\n",
    "                ans = max(ans, diff_with_b[ch][i], diff_with_b[i][ch])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for a in set(s):\n",
    "            for b in set(s):\n",
    "                if a!=b:\n",
    "                    diff, diff_with_b = 0, -inf\n",
    "                    for ch in s:\n",
    "                        if ch == a:\n",
    "                            diff += 1\n",
    "                            diff_with_b += 1\n",
    "                        elif ch == b:\n",
    "                            diff -= 1\n",
    "                            diff_with_b = diff  # 记录包含 b 时的 diff\n",
    "                            if diff < 0:\n",
    "                                diff = 0\n",
    "                        if diff_with_b > ans:\n",
    "                            ans = diff_with_b\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for a, b in permutations(ascii_lowercase, 2):\n",
    "            diff, diff_with_b = 0, -inf\n",
    "            for ch in s:\n",
    "                if ch == a:\n",
    "                    diff += 1\n",
    "                    diff_with_b += 1\n",
    "                elif ch == b:\n",
    "                    diff -= 1\n",
    "                    diff_with_b = diff  # 记录包含 b 时的 diff\n",
    "                    if diff < 0:\n",
    "                        diff = 0\n",
    "                if diff_with_b > ans:\n",
    "                    ans = diff_with_b\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for a, b in permutations(ascii_lowercase, 2):\n",
    "            diff, diff_B = 0, -inf\n",
    "            for ch in s:\n",
    "                if ch == a:\n",
    "                    diff += 1\n",
    "                    diff_B += 1\n",
    "                elif ch == b:\n",
    "                    diff -= 1\n",
    "                    diff_B = diff\n",
    "                    if diff < 0: # not diff_B\n",
    "                        diff = 0\n",
    "                if diff_B > res:\n",
    "                    res = diff_B\n",
    "        return res\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/substring-with-largest-variance/solutions/1494890/by-endlesscheng-5775/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "class Solution:\n",
    "  def largestVariance(self, s: str) -> int:\n",
    "    def func1(iter_s,a,b):\n",
    "      c=next(iter_s)\n",
    "      if c==a:\n",
    "          len=1\n",
    "          for c in iter_s:\n",
    "              if c==b:\n",
    "                  return mode1(len,iter_s,a)\n",
    "              len+=1\n",
    "      else:\n",
    "          return mode2(iter_s,a)\n",
    "      return 0\n",
    "    \n",
    "    def get_it(s,a,b):\n",
    "      for v in s:\n",
    "          if v==a or v==b:\n",
    "              yield v\n",
    "\n",
    "    def func1(iter_s,a,b):\n",
    "      c=next(iter_s)\n",
    "      if c==a:\n",
    "          len=1\n",
    "          for c in iter_s:\n",
    "              if c==b:\n",
    "                  return mode1(len,iter_s,a)\n",
    "              len+=1\n",
    "      else:\n",
    "          return mode2(iter_s,a)\n",
    "      return 0\n",
    "      \n",
    "    def mode1(len,iter_s,a):\n",
    "      res=len-1\n",
    "      curr=res\n",
    "      for v in iter_s:\n",
    "          if v==a:\n",
    "              curr+=1\n",
    "              res=max(res,curr)\n",
    "          else:\n",
    "              if curr==0:\n",
    "                  return mode2(iter_s,a)\n",
    "              curr-=1\n",
    "      return res\n",
    "    def mode2(iter_s,a):\n",
    "      curr=0\n",
    "      for v in iter_s:\n",
    "          if v==a:\n",
    "              curr+=1\n",
    "          else:\n",
    "              if curr>0:\n",
    "                  return mode1(curr,iter_s,a)\n",
    "      if curr==0:\n",
    "          return 0\n",
    "      return curr-1\n",
    "\n",
    "    res=0\n",
    "    for a,b in permutations(set(s), 2):\n",
    "      iters = get_it(s,a,b)\n",
    "      res = max(res, func1(iters,a,b))\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        for a, b in permutations(ascii_lowercase, 2):\n",
    "            diff = 0\n",
    "            i = 0\n",
    "            while i < n and (ch := s[i]) != b:\n",
    "                if ch == a:\n",
    "                    diff += 1\n",
    "                i += 1\n",
    "            if i == n:\n",
    "                continue\n",
    "            assert s[i] == b\n",
    "\n",
    "            while i < n:\n",
    "                assert s[i] == b\n",
    "                i += 1\n",
    "                if diff == 0:\n",
    "                    while i < n:\n",
    "                        if (ch := s[i]) == b and diff > 0:\n",
    "                            break\n",
    "                        if ch == a:\n",
    "                            diff += 1\n",
    "                        i += 1\n",
    "                    if diff > 0:\n",
    "                        ans = max(ans, diff-1)\n",
    "                    i += 1\n",
    "                diff -= 1\n",
    "                while i < n and (ch := s[i]) != b:\n",
    "                    if ch == a:\n",
    "                        diff += 1\n",
    "                    i += 1\n",
    "                ans = max(ans, diff)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for a, b in itertools.permutations(string.ascii_lowercase, 2):\n",
    "            if a == b:\n",
    "                    continue\n",
    "            dp0, dp1 = 0, -114514\n",
    "            for c in s:\n",
    "                if c == b:\n",
    "                    dp1 = max(dp1 - 1, dp0 - 1)\n",
    "                    dp0 = 0\n",
    "                elif c == a:\n",
    "                    dp1 += 1\n",
    "                    dp0 += 1\n",
    "                res = max(res, dp1)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def func(self,s,a,b):\n",
    "        for c in s:\n",
    "            if c in (a,b):\n",
    "                yield c\n",
    "    def largestVariance(self, s):\n",
    "        res=0\n",
    "        for a,b in permutations(set(s),2):\n",
    "            iters=self.func(s,a,b)\n",
    "            res=max(res,self.func1(iters,a,b))\n",
    "        return res\n",
    "    def func1(self,iters,a,b):#a大，b小\n",
    "        c=next(iters)\n",
    "        if c==a:\n",
    "            n=1\n",
    "            for ch in iters:\n",
    "                if ch == b:\n",
    "                    return self.mode1(n, iters, a)\n",
    "                n += 1\n",
    "\n",
    "        else:\n",
    "            return self.mode2(iters,a)\n",
    "        return 0\n",
    "\n",
    "    def mode1(self,n,iters,a):\n",
    "        res=n-1\n",
    "        tep=res\n",
    "        for ch in iters:\n",
    "            if ch == a:\n",
    "                tep+=1\n",
    "                res=max(res,tep)\n",
    "                continue\n",
    "            if tep==0:\n",
    "                return self.mode2(iters,a)\n",
    "            tep -= 1\n",
    "        return res\n",
    "\n",
    "    def mode2(self,iters,a):\n",
    "        for v in iters:\n",
    "            if v == a:\n",
    "                break\n",
    "        else:\n",
    "            return 0\n",
    "        n=1\n",
    "        for ch in iters:\n",
    "            if ch == a:\n",
    "                n+=1\n",
    "                continue\n",
    "            return self.mode1(n, iters, a)\n",
    "        return n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        for a, b in permutations(ascii_lowercase, 2):\n",
    "            diff = 0\n",
    "            i = 0\n",
    "            while i < n and (ch := s[i]) != b:\n",
    "                if ch == a:\n",
    "                    diff += 1\n",
    "                i += 1\n",
    "            if i == n:\n",
    "                continue\n",
    "            assert s[i] == b\n",
    "\n",
    "            while i < n:\n",
    "                assert s[i] == b\n",
    "                i += 1\n",
    "                if diff == 0:\n",
    "                    while i < n:\n",
    "                        if (ch := s[i]) == b and diff > 0:\n",
    "                            break\n",
    "                        if ch == a:\n",
    "                            diff += 1\n",
    "                        i += 1\n",
    "                    i += 1\n",
    "                diff -= 1\n",
    "                while i < n and (ch := s[i]) != b:\n",
    "                    if ch == a:\n",
    "                        diff += 1\n",
    "                    i += 1\n",
    "                ans = max(ans, diff)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for a, b in itertools.permutations(set(s), 2):\n",
    "            diff, diff_with_b = 0, -inf\n",
    "            for ch in s:\n",
    "                if ch == a:\n",
    "                    diff += 1\n",
    "                    diff_with_b += 1\n",
    "                    ans = max(ans, diff_with_b)\n",
    "                elif ch == b:\n",
    "                    diff_with_b = diff-1  # 记录包含 b 时的 diff\n",
    "                    diff = max(0, diff_with_b)\n",
    "                    ans = max(ans, diff_with_b)\n",
    "                else:\n",
    "                    continue\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        key = Counter(s).keys()\n",
    "        ans = 0\n",
    "        for high_ch in key:\n",
    "            for low_ch in key:\n",
    "                if high_ch != low_ch:\n",
    "                    f, g = 0, float(\"-inf\")\n",
    "                    for index in range(len(s)):\n",
    "                        if s[index] == high_ch:\n",
    "                            f, g = max(f, 0) + 1, g + 1\n",
    "                        elif s[index] == low_ch:\n",
    "                            f, g = max(f, 0) - 1, max(f, g, 0) - 1\n",
    "                        ans = max(ans, g)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for a, b in permutations(ascii_lowercase, 2):\n",
    "            diff, diff_with_b = 0, -inf\n",
    "            for ch in s:\n",
    "                if ch == a:\n",
    "                    diff += 1\n",
    "                    diff_with_b += 1\n",
    "                elif ch == b:\n",
    "                    diff -= 1\n",
    "                    diff_with_b = diff\n",
    "                    if diff < 0:\n",
    "                        diff = 0\n",
    "                if diff_with_b > ans:\n",
    "                    ans = diff_with_b\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for a, b in permutations(ascii_lowercase, 2):\n",
    "            diff, diff_with_b = 0, -inf\n",
    "            for ch in s:\n",
    "                if ch == a:\n",
    "                    diff += 1\n",
    "                    diff_with_b += 1\n",
    "                elif ch == b:\n",
    "                    diff -= 1\n",
    "                    diff_with_b = diff  # 记录包含 b 时的 diff\n",
    "                    if diff < 0:\n",
    "                        diff = 0\n",
    "                if diff_with_b > ans:\n",
    "                    ans = diff_with_b\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for a, b in permutations(ascii_lowercase, 2):\n",
    "            diff = 0\n",
    "            flg = inf\n",
    "            for ch in s:\n",
    "                if ch == a:\n",
    "                    diff += 1\n",
    "                    ans = max(ans, diff - flg)\n",
    "                elif ch == b:\n",
    "                    if diff == 0:\n",
    "                        flg = 1\n",
    "                    else:\n",
    "                        flg = 0\n",
    "                        diff -= 1\n",
    "                        ans = max(ans, diff)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import permutations\n",
    "def func2(s1,s2,s):\n",
    "    for ss in s:\n",
    "        if ss in (s1,s2):\n",
    "            yield ss\n",
    "def mode1(s1,sum_s1,iter_s):\n",
    "    res = sum_s1-1\n",
    "    res1 = res\n",
    "    for s in iter_s:\n",
    "        if s == s1:\n",
    "            res1 += 1\n",
    "            res = max(res,res1)\n",
    "        else:\n",
    "            if res1 == 0:\n",
    "                return mode2(s1,iter_s)\n",
    "            res1 -= 1\n",
    "    return res\n",
    "def mode2(s1,iter_s):\n",
    "    for s in iter_s:\n",
    "        if s == s1:\n",
    "            break\n",
    "    else:\n",
    "        return 0\n",
    "    sum_s1 = 1\n",
    "    for ss in iter_s:\n",
    "        if ss != s1:\n",
    "            return mode1(s1,sum_s1,iter_s)\n",
    "        sum_s1 += 1\n",
    "    return sum_s1-1\n",
    "\n",
    "def func1(s1,s2,iter_s):\n",
    "    c = next(iter_s)\n",
    "    if c == s1:\n",
    "        sum_s1 = 1\n",
    "        for s in iter_s:\n",
    "            if s == s2:\n",
    "                return mode1(s1,sum_s1,iter_s)\n",
    "            sum_s1 += 1\n",
    "    else:\n",
    "        return mode2(s1,iter_s)\n",
    "    return 0\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for s1,s2 in permutations(set(s),2):\n",
    "            iter_s = func2(s1,s2,s)\n",
    "            ans = max(ans,func1(s1,s2,iter_s))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "\n",
    "\n",
    "def yield_s(s1, s2, s):\n",
    "    for v in s:\n",
    "        if v in (s1, s2):\n",
    "            yield v\n",
    "\n",
    "\n",
    "def mod1(a, num, iters):\n",
    "    num -= 1\n",
    "    res = num\n",
    "    for c in iters:\n",
    "        if c == a:\n",
    "            num += 1\n",
    "            res = max(res, num)\n",
    "            continue\n",
    "        if num == 0:\n",
    "            return max(res, mod2(a, iters))\n",
    "        num -= 1\n",
    "    return res\n",
    "\n",
    "\n",
    "def mod2(a, iters):\n",
    "    for x in iters:\n",
    "        if x == a:\n",
    "            break\n",
    "    numa = 1\n",
    "    for x in iters:\n",
    "        if x == a:\n",
    "            numa += 1\n",
    "            continue\n",
    "        # 碰到b\n",
    "        return mod1(a, numa, iters)\n",
    "    return numa - 1\n",
    "\n",
    "\n",
    "def func1(a, b, iters):  # a多，b少\n",
    "    c = next(iters)\n",
    "    if c == a:  # 第一个是a\n",
    "        numa = 1\n",
    "        for x in iters:\n",
    "            if x == b:\n",
    "                return mod1(a, numa, iters)\n",
    "            numa += 1\n",
    "        else:\n",
    "            return 0    # 全a全b返回0\n",
    "    else:  # 第一个是b\n",
    "        return mod2(a, iters)\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for s1, s2 in list(itertools.permutations(set(s), 2)):\n",
    "            res = max(res, func1(s1, s2, yield_s(s1, s2, s)))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        def func1(iter_s, a, b):\n",
    "            c = next(iter_s)\n",
    "            if c == a:\n",
    "                lena = 1\n",
    "                for c in iter_s:\n",
    "                    if c == b:\n",
    "                        return model1(lena, iter_s, a)\n",
    "                    lena += 1\n",
    "            else:\n",
    "                return model2(iter_s, a)\n",
    "            return 0\n",
    "        def func2(s, alph1, alph2):\n",
    "            for alph in s:\n",
    "                if alph==alph1 or alph==alph2:\n",
    "                    yield alph\n",
    "        def model1(lena, iter_s, a):\n",
    "            res = lena - 1\n",
    "            curr = res\n",
    "            for x in iter_s:\n",
    "                if x == a:\n",
    "                    curr += 1\n",
    "                    res = max(res, curr)\n",
    "                else:\n",
    "                    if curr == 0:\n",
    "                        return model2(iter_s, a)\n",
    "                    curr -= 1\n",
    "            return res\n",
    "\n",
    "        def model2(iter_s, a):\n",
    "            curr=0\n",
    "            for x in iter_s:\n",
    "                if x==a:\n",
    "                    curr+=1\n",
    "                else:\n",
    "                    if curr>0:\n",
    "                        return model1(curr,iter_s,a)\n",
    "            if curr==0:\n",
    "                return 0\n",
    "            return curr-1\n",
    "        res=0\n",
    "        for alph1,alph2 in permutations(set(s),2):\n",
    "            iters=func2(s,alph1,alph2)\n",
    "            res = max(res, func1(iters, alph1, alph2))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for a, b in permutations(ascii_lowercase, 2):\n",
    "            diff, diff_with_b = 0, -inf\n",
    "            for ch in s:\n",
    "                if ch == a:\n",
    "                    diff += 1\n",
    "                    diff_with_b += 1\n",
    "                elif ch == b:\n",
    "                    diff -= 1\n",
    "                    diff_with_b = diff # 记录包含b时的dif\n",
    "                    if diff < 0:\n",
    "                        diff = 0\n",
    "                if diff_with_b > ans:\n",
    "                    ans = diff_with_b\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for A in range(26):\n",
    "            a = chr(A+ord('a'))\n",
    "            for B in range(26):\n",
    "                if B == A:continue\n",
    "                temp = 0\n",
    "                b = chr(B+ord('a'))\n",
    "                diff,diff_with_b = 0,-inf\n",
    "                st1 = []\n",
    "                st2 = []\n",
    "                mn = 0\n",
    "                for ch in s:\n",
    "                    if ch == a:\n",
    "                        diff += 1\n",
    "                        diff_with_b += 1\n",
    "                    elif ch == b:\n",
    "                        diff -= 1\n",
    "                        diff_with_b = diff  # 记录包含 b 时的 diff\n",
    "                        if diff < 0:\n",
    "                            diff = 0\n",
    "                    if diff_with_b > res:\n",
    "                        res = diff_with_b\n",
    "\n",
    "        return res\n",
    "                    \n",
    "                    \n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "\n",
    "\n",
    "def yield_s(s1, s2, s):\n",
    "    for v in s:\n",
    "        if v in (s1, s2):\n",
    "            yield v\n",
    "\n",
    "\n",
    "def mod1(a, num, iters):\n",
    "    num -= 1\n",
    "    res = num\n",
    "    for c in iters:\n",
    "        if c == a:\n",
    "            num += 1\n",
    "            res = max(res, num)\n",
    "            continue\n",
    "        if num == 0:\n",
    "            return max(res, mod2(a, iters))\n",
    "        num -= 1\n",
    "    return res\n",
    "\n",
    "\n",
    "def mod2(a, iters):\n",
    "    for x in iters:\n",
    "        if x == a:\n",
    "            break\n",
    "    numa = 1\n",
    "    for x in iters:\n",
    "        if x == a:\n",
    "            numa += 1\n",
    "            continue\n",
    "        # 碰到b\n",
    "        return mod1(a, numa, iters)\n",
    "    return numa - 1\n",
    "\n",
    "\n",
    "def func1(a, b, iters):  # a多，b少\n",
    "    c = next(iters)\n",
    "    if c == a:  # 第一个是a\n",
    "        numa = 1\n",
    "        for x in iters:\n",
    "            if x == b:\n",
    "                return mod1(a, numa, iters)\n",
    "            numa += 1\n",
    "        else:\n",
    "            return 0    # 全a全b返回0\n",
    "    else:  # 第一个是b\n",
    "        return mod2(a, iters)\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for s1, s2 in itertools.permutations(set(s), 2):\n",
    "            res = max(res, func1(s1, s2, yield_s(s1, s2, s)))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    " \n",
    "        ans = 0\n",
    "        for a in set(s):\n",
    "            for b in set(s):\n",
    "                if a!=b:\n",
    "                    c, d = 0, -float('inf')\n",
    "                    for j in s:\n",
    "                        if j==b:\n",
    "                            c = max(-1, c-1)\n",
    "                            d = c\n",
    "                        elif j==a:\n",
    "                            c = max(1, c+1)\n",
    "                            d = d+1\n",
    "                        else:\n",
    "                            c = max(c, 0) \n",
    "                            d = d \n",
    "                       \n",
    "                        ans = max(ans, d)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        diff = [[[0, - float('inf')] for _ in range(26)] for _ in range(26)]\n",
    "        for i in range(n):\n",
    "            v1 = ord(s[i]) - ord('a')\n",
    "            for v2 in range(26):\n",
    "                diff[v1][v2][0] += 1 \n",
    "                diff[v1][v2][1] += 1\n",
    "                diff[v2][v1][0], diff[v2][v1][1] = max(max(diff[v2][v1][0], diff[v2][v1][1]) - 1, 0), max(max(diff[v2][v1][0], diff[v2][v1][1]) - 1, - 1)\n",
    "                res = max(res, diff[v1][v2][1], diff[v2][v1][1])\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for a, b in permutations(ascii_lowercase, 2):\n",
    "            diff, diff_with_b = 0, -inf\n",
    "            for ch in s:\n",
    "                if ch == a:\n",
    "                    diff += 1\n",
    "                    diff_with_b += 1\n",
    "                elif ch == b:\n",
    "                    diff -= 1\n",
    "                    diff_with_b = diff  # 记录包含 b 时的 diff\n",
    "                    if diff < 0:\n",
    "                        diff = 0\n",
    "                if diff_with_b > ans:\n",
    "                    ans = diff_with_b\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for a, b in permutations(ascii_lowercase, 2):\n",
    "            diff = 0\n",
    "            diff_with_b = -inf \n",
    "            for ch in s:\n",
    "                if ch == a:\n",
    "                    diff += 1\n",
    "                    diff_with_b += 1                    \n",
    "                elif ch == b:\n",
    "                    diff -= 1\n",
    "                    diff_with_b = diff\n",
    "                    if diff < 0:\n",
    "                        diff = 0\n",
    "                if diff_with_b > ans:\n",
    "                    ans = diff_with_b\n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "class Solution:\n",
    "  def largestVariance(self, s: str) -> int:\n",
    "    def func1(iter_s,a,b):\n",
    "      c=next(iter_s)\n",
    "      if c==a:\n",
    "          len=1\n",
    "          for c in iter_s:\n",
    "              if c==b:\n",
    "                  return mode1(len,iter_s,a)\n",
    "              len+=1\n",
    "      else:\n",
    "          return mode2(iter_s,a)\n",
    "      return 0\n",
    "    \n",
    "    def get_s(s,a,b):\n",
    "      for v in s:\n",
    "          if v==a or v==b:\n",
    "              yield v\n",
    "\n",
    "    def func1(iter_s,a,b):\n",
    "      c=next(iter_s)\n",
    "      if c==a:\n",
    "          len=1\n",
    "          for c in iter_s:\n",
    "              if c==b:\n",
    "                  return mode1(len,iter_s,a)\n",
    "              len+=1\n",
    "      else:\n",
    "          return mode2(iter_s,a)\n",
    "      return 0\n",
    "      \n",
    "    def mode1(len,iter_s,a):\n",
    "      res=len-1\n",
    "      curr=res\n",
    "      for v in iter_s:\n",
    "          if v==a:\n",
    "              curr+=1\n",
    "              res=max(res,curr)\n",
    "          else:\n",
    "              if curr==0:\n",
    "                  return mode2(iter_s,a)\n",
    "              curr-=1\n",
    "      return res\n",
    "    def mode2(iter_s,a):\n",
    "      curr=0\n",
    "      for x in iter_s:\n",
    "          if x==a:\n",
    "              curr+=1\n",
    "          else:\n",
    "              if curr>0:\n",
    "                  return mode1(curr,iter_s,a)\n",
    "      if curr==0:\n",
    "          return 0\n",
    "      return curr-1\n",
    "    res=0\n",
    "    for a,b in permutations(set(s), 2):\n",
    "      iters = get_s(s,a,b)\n",
    "      res = max(res, func1(iters,a,b))\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self,s):\n",
    "        def func1(iter_s, a, b):\n",
    "            c = next(iter_s)\n",
    "            if c == a:\n",
    "                lena = 1\n",
    "                for c in iter_s:\n",
    "                    if c == b:\n",
    "                        return model1(lena, iter_s, a)\n",
    "                    lena += 1\n",
    "            else:\n",
    "                return model2(iter_s, a)\n",
    "            return 0\n",
    "        def func2(s, alph1, alph2):\n",
    "            for alph in s:\n",
    "                if alph in (alph1, alph2):\n",
    "                    yield alph\n",
    "        def model1(lena, iter_s, a):\n",
    "            res = lena - 1\n",
    "            curr = res\n",
    "            for x in iter_s:\n",
    "                if x == a:\n",
    "                    curr += 1\n",
    "                    res = max(res, curr)\n",
    "                else:\n",
    "                    if curr == 0:\n",
    "                        return model2(iter_s, a)\n",
    "                    curr -= 1\n",
    "            return res\n",
    "\n",
    "        def model2(iter_s, a):\n",
    "\n",
    "            for x in iter_s:\n",
    "                if x == a:\n",
    "                    break\n",
    "            else:\n",
    "                return 0\n",
    "            curr = 1\n",
    "            for x1 in iter_s:\n",
    "                if x1 == a:\n",
    "                    curr += 1\n",
    "                else:\n",
    "                    return model1(curr, iter_s, a)\n",
    "            return curr - 1\n",
    "        res=0\n",
    "        for alph1,alph2 in permutations(set(s),2):\n",
    "            iters=func2(s,alph1,alph2)\n",
    "            res = max(res, func1(iters, alph1, alph2))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            # curr=0\n",
    "            # for x in iter_s:\n",
    "            #     if x==a:\n",
    "            #         curr+=1\n",
    "            #     else:\n",
    "            #         if curr>0:\n",
    "            #             return model1(curr,iter_s,a)\n",
    "            # if curr==0:\n",
    "            #     return 0\n",
    "            # return curr-1\n",
    "\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    " \n",
    "        ans = 0\n",
    "        for a in set(s):\n",
    "            for b in set(s):\n",
    "                if a!=b:\n",
    "                    c, d = 0, -float('inf')\n",
    "                    for j in s:\n",
    "                        if j==b:\n",
    "                            c = max(-1, c-1)\n",
    "                            d = c\n",
    "                        elif j==a:\n",
    "                            c = max(1, c+1)\n",
    "                            d = d+1\n",
    "                        else:\n",
    "                            c = max(c, 0) \n",
    "                            d = d \n",
    "                        if d>ans:\n",
    "                            ans = d\n",
    "                       \n",
    "                        # ans = max(ans, d)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    " \n",
    "        ans = 0\n",
    "        for a in set(s):\n",
    "            for b in set(s):\n",
    "                if a!=b:\n",
    "                    c, d = 0, -float('inf')\n",
    "                    for j in s:\n",
    "                        if j==b:\n",
    "                            if c>0:\n",
    "                                c = c-1 \n",
    "                            else:\n",
    "                                c = -1 \n",
    "                         \n",
    "                            d = c\n",
    "                        elif j==a:\n",
    "                            if c>0:\n",
    "                                c = c+1 \n",
    "                            else:\n",
    "                                c = 1 \n",
    "                     \n",
    "                            d = d+1\n",
    "                        else:\n",
    "                            if c>0:\n",
    "                                c = c \n",
    "                            else:\n",
    "                                c = 0 \n",
    "                          \n",
    "                            d = d \n",
    "                        if d>ans:\n",
    "                            ans = d\n",
    "                       \n",
    "                        # ans = max(ans, d)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import permutations\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for c1,c2 in list(permutations(set(s),2)):\n",
    "            iter_s = func2(c1,c2,s)\n",
    "            res = max(res,func1(c1,c2,iter_s))\n",
    "        return res\n",
    "\n",
    "def func2(a,b,s):\n",
    "    for v in s:\n",
    "        if v in (a,b):\n",
    "            yield v\n",
    "\n",
    "def func1(a,b,iter_s):\n",
    "    c = next(iter_s)\n",
    "    if c == a:\n",
    "        n = 1\n",
    "        for x in iter_s:\n",
    "            if x == b:\n",
    "                return mode1(a,n,iter_s)\n",
    "            n += 1\n",
    "    elif c == b:\n",
    "        return mode2(a,iter_s)\n",
    "\n",
    "    return 0\n",
    "\n",
    "def mode1(a,n,iter_s):\n",
    "    res = n - 1\n",
    "    max_res = res\n",
    "    for v in iter_s:\n",
    "        if v == a:\n",
    "            res += 1\n",
    "            max_res = max(max_res,res)\n",
    "        else:\n",
    "            res -= 1\n",
    "            if res < 0:\n",
    "                max_res = max(max_res,mode2(a,iter_s))\n",
    "    return max_res\n",
    "\n",
    "def mode2(a,iter_s):\n",
    "    for v1 in iter_s:\n",
    "        if v1 == a:\n",
    "            break\n",
    "    else:\n",
    "        return 0\n",
    "    tmp = 1\n",
    "    for v2 in iter_s:\n",
    "        if v2 != a:\n",
    "            return mode1(a, tmp, iter_s)\n",
    "        tmp += 1\n",
    "    return tmp - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for a, b in permutations(ascii_lowercase, 2): #26*25\n",
    "            # print(a, b)\n",
    "            diff = 0\n",
    "            diff_B = -inf\n",
    "            for ch in s:\n",
    "                if ch == a:\n",
    "                    diff += 1\n",
    "                    diff_B += 1\n",
    "                elif ch == b:\n",
    "                    diff -= 1\n",
    "                    diff_B = diff\n",
    "                    if diff < 0:\n",
    "                        diff = 0\n",
    "                res = max(res, diff_B)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for ch1, ch2 in permutations(ascii_lowercase, 2):\n",
    "            diff = 0\n",
    "            diff_ch2 = -inf\n",
    "            for ch in s:\n",
    "                if ch == ch1:\n",
    "                    diff += 1\n",
    "                    diff_ch2 += 1\n",
    "                elif ch == ch2:\n",
    "                    diff -= 1\n",
    "                    diff_ch2 = diff\n",
    "                    if diff < 0:\n",
    "                        diff = 0\n",
    "                res = max(res, diff_ch2)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "class Solution:\n",
    "  def largestVariance(self, s: str) -> int:\n",
    "    def func1(iter_s,a,b):\n",
    "      c=next(iter_s)\n",
    "      if c==a:\n",
    "          len=1\n",
    "          for c in iter_s:\n",
    "              if c==b:\n",
    "                  return mode1(len,iter_s,a)\n",
    "              len+=1\n",
    "      else:\n",
    "          return mode2(iter_s,a)\n",
    "      return 0\n",
    "    \n",
    "    def get_s(s,a,b):\n",
    "      for v in s:\n",
    "          if v==a or v==b:\n",
    "              yield v\n",
    "\n",
    "    def func1(iter_s,a,b):\n",
    "      c=next(iter_s)\n",
    "      if c==a:\n",
    "          len=1\n",
    "          for c in iter_s:\n",
    "              if c==b:\n",
    "                  return mode1(len,iter_s,a)\n",
    "              len+=1\n",
    "      else:\n",
    "          return mode2(iter_s,a)\n",
    "      return 0\n",
    "      \n",
    "    def mode1(len,iter_s,a):\n",
    "      res=len-1\n",
    "      curr=res\n",
    "      for v in iter_s:\n",
    "          if v==a:\n",
    "              curr+=1\n",
    "              res=max(res,curr)\n",
    "          else:\n",
    "              if curr==0:\n",
    "                  return mode2(iter_s,a)\n",
    "              curr-=1\n",
    "      return res\n",
    "    def mode2(iter_s,a):\n",
    "      curr=0\n",
    "      for x in iter_s:\n",
    "          if x==a:\n",
    "              curr+=1\n",
    "          else:\n",
    "              if curr>0:\n",
    "                  return mode1(curr,iter_s,a)\n",
    "      if curr==0:\n",
    "          return 0\n",
    "      return curr-1\n",
    "    res=0\n",
    "    for a,b in permutations(set(s), 2):\n",
    "      iters = get_s(s,a,b)\n",
    "      res = max(res, func1(iters,a,b))\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "max_ = lambda a, b: a if a >= b else b\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        nums = [ord(ch) - 97 for ch in s]\n",
    "        unique = list(set(nums))\n",
    "        if len(unique) == 1:\n",
    "            return 0\n",
    "\n",
    "        ans = 0\n",
    "        diff0 = [[0] * 26 for _ in range(26)]\n",
    "        diff1 = [[-10001] * 26 for _ in range(26)]\n",
    "        for x in nums:\n",
    "            for y in unique:\n",
    "                if x == y:\n",
    "                    continue\n",
    "                diff0[x][y] += 1\n",
    "                diff1[x][y] += 1\n",
    "                diff0[y][x] -= 1\n",
    "                diff1[y][x] = diff0[y][x]\n",
    "                diff0[y][x] = max_(diff0[y][x], 0)\n",
    "                ans = max_(ans, max_(diff1[x][y], diff1[y][x]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for a, b in permutations(set(s), 2):\n",
    "            diff = 0\n",
    "            diff_with_b = -inf \n",
    "            for ch in s:\n",
    "                if ch == a:\n",
    "                    diff += 1\n",
    "                    diff_with_b += 1                    \n",
    "                elif ch == b:\n",
    "                    diff -= 1\n",
    "                    diff_with_b = diff\n",
    "                    if diff < 0:\n",
    "                        diff = 0\n",
    "                if diff_with_b > ans:\n",
    "                    ans = diff_with_b\n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans=0\n",
    "        for i in range(26):\n",
    "            a=chr(ord('a')+i)\n",
    "            for j in range(26):\n",
    "                b=chr(ord('a')+j)\n",
    "                if a==b:\n",
    "                    continue\n",
    "                diff_withb=-float('inf')\n",
    "                diff=0\n",
    "                for ch in s:\n",
    "                    if ch == a:\n",
    "                        diff+=1\n",
    "                        diff_withb+=1\n",
    "                    elif ch == b:\n",
    "                        diff-=1\n",
    "                        diff_withb=diff\n",
    "                        diff=max(diff,0)\n",
    "                    ans=max(ans, diff_withb)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/problems/substring-with-largest-variance/solutions/1494890/by-endlesscheng-5775\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for a, b in permutations(set(s), 2):\n",
    "            diff, diff_with_b = 0, -inf\n",
    "            for ch in s:\n",
    "                if ch == a:\n",
    "                    diff += 1\n",
    "                    diff_with_b += 1\n",
    "                elif ch == b:\n",
    "                    diff -= 1\n",
    "                    diff_with_b = diff\n",
    "                    if diff < 0:\n",
    "                        diff = 0\n",
    "                ans = max(ans, diff_with_b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for a, b in permutations(ascii_lowercase, 2):\n",
    "            diff, diff_with_b = 0, -inf\n",
    "            for ch in s:\n",
    "                if ch == a:\n",
    "                    diff += 1\n",
    "                    diff_with_b += 1\n",
    "                elif ch == b:\n",
    "                    diff -= 1\n",
    "                    diff_with_b = diff  # 记录包含 b 时的 diff\n",
    "                    if diff < 0:\n",
    "                        diff = 0\n",
    "                if diff_with_b > ans:\n",
    "                    ans = diff_with_b\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    '''\r\n",
    "    def largestVariance(self, s: str) -> int:\r\n",
    "        ans = 0\r\n",
    "        for a, b in permutations(ascii_lowercase, 2):\r\n",
    "            diff, diff_with_b = 0, -inf\r\n",
    "            for ch in s:\r\n",
    "                if ch == a:\r\n",
    "                    diff += 1\r\n",
    "                    diff_with_b += 1\r\n",
    "                elif ch == b:\r\n",
    "                    diff -= 1\r\n",
    "                    diff_with_b = diff  # 记录包含 b 时的 diff\r\n",
    "                    if diff < 0:\r\n",
    "                        diff = 0\r\n",
    "                if diff_with_b > ans:\r\n",
    "                    ans = diff_with_b\r\n",
    "        return ans\r\n",
    "    '''\r\n",
    "\r\n",
    "    # 在遍历 s 的过程中将 s[i] 作为 a 或 b，减少枚举次数，从而优化时间复杂度\r\n",
    "    def largestVariance(self, s: str) -> int:\r\n",
    "        if s.count(s[0]) == len(s):\r\n",
    "            return 0\r\n",
    "        ans = 0\r\n",
    "        diff = [[0] * 26 for _ in range(26)]\r\n",
    "        diff_with_b = [[-inf] * 26 for _ in range(26)]\r\n",
    "        for ch in s:\r\n",
    "            ch = ord(ch) - ord('a')\r\n",
    "            for i in range(26):\r\n",
    "                if i == ch:\r\n",
    "                    continue\r\n",
    "                diff[ch][i] += 1  # a=ch, b=i\r\n",
    "                diff_with_b[ch][i] += 1\r\n",
    "                diff[i][ch] -= 1  # a=i, b=ch\r\n",
    "                diff_with_b[i][ch] = diff[i][ch]\r\n",
    "                if diff[i][ch] < 0:\r\n",
    "                    diff[i][ch] = 0\r\n",
    "                ans = max(ans, diff_with_b[ch][i], diff_with_b[i][ch])\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "max_ = lambda a, b: a if a >= b else b\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        nums = [ord(ch) - 97 for ch in s]\n",
    "        unique = list(set(nums))\n",
    "        if len(unique) == 1:\n",
    "            return 0\n",
    "\n",
    "        ans = 0\n",
    "        diff0 = [[0] * 26 for _ in range(26)]\n",
    "        diff1 = [[-inf] * 26 for _ in range(26)]\n",
    "        for x in nums:\n",
    "            for y in unique:\n",
    "                if x == y:\n",
    "                    continue\n",
    "                diff0[x][y] += 1\n",
    "                diff1[x][y] += 1\n",
    "                diff0[y][x] -= 1\n",
    "                diff1[y][x] = diff0[y][x]\n",
    "                diff0[y][x] = max_(diff0[y][x], 0)\n",
    "                ans = max_(ans, max_(diff1[x][y], diff1[y][x]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for a, b in permutations(ascii_lowercase, 2):\n",
    "            diff, diff_with_b = 0, -inf\n",
    "            for ch in s:\n",
    "                if ch == a:\n",
    "                    diff += 1\n",
    "                    diff_with_b += 1\n",
    "                elif ch == b:\n",
    "                    diff -= 1\n",
    "                    diff_with_b = diff  # 记录包含 b 时的 diff\n",
    "                    if diff < 0:\n",
    "                        diff = 0\n",
    "                if diff_with_b > ans:\n",
    "                    ans = diff_with_b\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        if all(i == 1 for i in Counter(s).values()):\n",
    "            return 0\n",
    "        if s == s[0] * len(s):\n",
    "            return 0\n",
    "        n = len(s)\n",
    "        ret = 1\n",
    "        z = set(s)\n",
    "        for a in z:\n",
    "            for b in z:\n",
    "                if a != b:\n",
    "                    flag = False\n",
    "                    t = 0\n",
    "                    for c in s:\n",
    "                        if c == a:\n",
    "                            t += 1\n",
    "                        elif c == b:\n",
    "                            flag = True\n",
    "                            t -= 1\n",
    "                        if t < 0:\n",
    "                            flag = False\n",
    "                            t = 0\n",
    "                        if flag:\n",
    "                            ret = max(ret, t)\n",
    "                        if not flag:\n",
    "                            ret = max(ret, t - 1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        pos=defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            pos[c].append(i)\n",
    "        ans=0\n",
    "        for c0, pos0 in pos.items():\n",
    "            for c1, pos1 in pos.items():\n",
    "                if c0!=c1:\n",
    "                    i=j=0\n",
    "                    f, g=0, float(\"-inf\")\n",
    "                    while i<len(pos0) or j<len(pos1):\n",
    "                        if j==len(pos1) or (i<len(pos0) and pos0[i]<pos1[j]):\n",
    "                            f, g=max(f, 0)+1, g+1\n",
    "                            i+=1\n",
    "                        else:\n",
    "                            f, g=max(f, 0)-1, max(f, g, 0)-1\n",
    "                            j+=1\n",
    "                        ans=max(ans, g)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "class Solution:\n",
    "  def largestVariance(self, s: str) -> int:\n",
    "    def func1(iter_s,a,b):\n",
    "      c=next(iter_s)\n",
    "      if c==a:\n",
    "          len=1\n",
    "          for c in iter_s:\n",
    "              if c==b:\n",
    "                  return mode1(len,iter_s,a)\n",
    "              len+=1\n",
    "      else:\n",
    "          return mode2(iter_s,a)\n",
    "      return 0\n",
    "    \n",
    "    def get_it(s,a,b):\n",
    "      for v in s:\n",
    "          if v==a or v==b:\n",
    "              yield v\n",
    "\n",
    "    def func1(iter_s,a,b):\n",
    "      c=next(iter_s)\n",
    "      if c==a:\n",
    "          len=1\n",
    "          for c in iter_s:\n",
    "              if c==b:\n",
    "                  return mode1(len,iter_s,a)\n",
    "              len+=1\n",
    "      else:\n",
    "          return mode2(iter_s,a)\n",
    "      return 0\n",
    "      \n",
    "    def mode1(len,iter_s,a):\n",
    "      res=len-1\n",
    "      sum=res\n",
    "      for v in iter_s:\n",
    "          if v==a:\n",
    "              sum+=1\n",
    "              res=max(res,sum)\n",
    "          else:\n",
    "              if sum==0:\n",
    "                  return mode2(iter_s,a)\n",
    "              sum-=1\n",
    "      return res\n",
    "\n",
    "    def mode2(iter_s,a):\n",
    "      sum=0\n",
    "      for v in iter_s:\n",
    "          if v==a:\n",
    "              sum+=1\n",
    "          else:\n",
    "              if sum>0:\n",
    "                  return mode1(sum,iter_s,a)\n",
    "      if sum==0:\n",
    "          return 0\n",
    "      return sum-1\n",
    "\n",
    "    res=0\n",
    "    for a,b in permutations(set(s), 2):\n",
    "      iters = get_it(s,a,b)\n",
    "      res = max(res, func1(iters,a,b))\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "max_ = lambda a, b: a if a >= b else b\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        nums = [ord(ch) - 97 for ch in s]\n",
    "        unique = list(set(nums))\n",
    "        if len(unique) == 1:\n",
    "            return 0\n",
    "\n",
    "        ans = 0\n",
    "        diff0 = [[0] * 26 for _ in range(26)]\n",
    "        diff1 = [[-inf] * 26 for _ in range(26)]\n",
    "        for x in nums:\n",
    "            for y in range(26):\n",
    "                if x == y:\n",
    "                    continue\n",
    "                diff0[x][y] += 1\n",
    "                diff1[x][y] += 1\n",
    "                diff0[y][x] -= 1\n",
    "                diff1[y][x] = diff0[y][x]\n",
    "                diff0[y][x] = max_(diff0[y][x], 0)\n",
    "                ans = max_(ans, max_(diff1[x][y], diff1[y][x]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def func1(self,a,b,iter_s):\n",
    "        c = next(iter_s)\n",
    "        if c == a:\n",
    "            numa = 1\n",
    "            for x in iter_s:\n",
    "                if x == b:\n",
    "                    return self.mode1(a,numa,iter_s)\n",
    "                numa += 1\n",
    "        else:\n",
    "            return self.mode2(a,iter_s)\n",
    "        return 0\n",
    "\n",
    "\n",
    "    def mode1(self,a,numa,iter_s):#aaaab\n",
    "        \n",
    "        res = numa - 1\n",
    "        curr = res\n",
    "        for c in iter_s:\n",
    "            if c == a:\n",
    "                curr += 1\n",
    "                res = max(res,curr)\n",
    "                continue\n",
    "            if curr == 0:\n",
    "                return self.mode2(a,iter_s)\n",
    "            curr -= 1\n",
    "        return res\n",
    "    def mode2(self,a,iter_s):#bbba\n",
    "        for v in iter_s:\n",
    "            if v == a:\n",
    "                break\n",
    "        else:\n",
    "            return 0\n",
    "        numa = 1\n",
    "        for c in iter_s:\n",
    "            if c == a:\n",
    "                numa += 1\n",
    "                continue\n",
    "            return self.mode1(a,numa,iter_s)\n",
    "        return numa - 1\n",
    "    def get_s(self,a,b,s):\n",
    "        for c in s:\n",
    "            if c in (a,b):\n",
    "                yield c\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for a,b in list(itertools.permutations(set(s), 2)):\n",
    "            iter_s = self.get_s(a,b,s)\n",
    "            res = max(res,self.func1(a,b,iter_s))\n",
    "            print(a, b ,res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        record=defaultdict(list)\n",
    "        for index,i in enumerate(s):\n",
    "            record[i].append(index)\n",
    "        ans=0\n",
    "        temp=list(record.keys())\n",
    "        for max_target in temp:\n",
    "            for min_target in temp:\n",
    "                if min_target!=max_target:\n",
    "                    rxz=0\n",
    "                    i=j=0\n",
    "                    f=0\n",
    "                    g=float('-inf')\n",
    "                    m=len(record[max_target])\n",
    "                    n=len(record[min_target])\n",
    "                    while i<m or j<n:\n",
    "                        if j==n or (i<m and record[max_target][i]<record[min_target][j]):\n",
    "                            f, g = max(f, 0) + 1, g + 1\n",
    "                            i+=1\n",
    "                        else:\n",
    "                            f, g = max(f, 0) - 1, max(f, g, 0) - 1                         \n",
    "                            j+=1\n",
    "                        ans=max(ans,g)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        pos = defaultdict(list)\n",
    "        for i, ch in enumerate(s):\n",
    "            pos[ch].append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for c0, pos0 in pos.items():\n",
    "            for c1, pos1 in pos.items():\n",
    "                if c0 != c1:\n",
    "                    i = j = 0\n",
    "                    f, g = 0, float(\"-inf\")\n",
    "                    while i < len(pos0) or j < len(pos1):\n",
    "                        if j == len(pos1) or (i < len(pos0) and pos0[i] < pos1[j]):\n",
    "                            f, g = max(f, 0) + 1, g + 1\n",
    "                            i += 1\n",
    "                        else:\n",
    "                            f, g = max(f, 0) - 1, max(f, g, 0) - 1\n",
    "                            j += 1\n",
    "                        ans = max(ans, g)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        pos = defaultdict(list)\n",
    "        for i, ch in enumerate(s):\n",
    "            pos[ch].append(i)\n",
    "        ans = 0\n",
    "        for c0, pos0 in pos.items():\n",
    "            for c1, pos1 in pos.items():\n",
    "                if c0 != c1:\n",
    "                    i = j = 0\n",
    "                    f, g = 0, float(\"-inf\")\n",
    "                    while i < len(pos0) or j < len(pos1):\n",
    "                        if j == len(pos1) or (i < len(pos0) and pos0[i] < pos1[j]):\n",
    "                            f, g = max(f, 0) + 1, g + 1\n",
    "                            i += 1\n",
    "                        else:\n",
    "                            f, g = max(f, 0) - 1, max(f, g, 0) - 1\n",
    "                            j += 1\n",
    "                        ans = max(ans, g)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        d=defaultdict(list)\n",
    "        r = 0\n",
    "        for i,v in enumerate(s):d[v].append(i)\n",
    "        for c1,s1 in d.items():\n",
    "            for c2,s2 in d.items():\n",
    "                if c1==c2:continue\n",
    "                i = j = 0\n",
    "                f, g = 0,-1000000\n",
    "                while i < len(s1) or j < len(s2):\n",
    "                    if j == len(s2) or (i < len(s1) and s1[i] < s2[j]):\n",
    "                        f, g = 1 if f<0 else f+1, g + 1\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        f, g = 0 if f<0 else f-1, max(f,0,g) - 1\n",
    "                        j += 1\n",
    "                    if g>r:r=g\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def largestVariance(self, s: str) -> int:\n",
    "#         if not s:\n",
    "#             return 0\n",
    "#         d={}\n",
    "#         for i,le in enumerate(s):\n",
    "#             if le not in d:\n",
    "#                 d[le] = 1\n",
    "#             else:\n",
    "#                 d[le] = d[le] + 1\n",
    "#         ans=0\n",
    "#         for a,c0 in enumerate(d):\n",
    "#             for b,c1 in enumerate(d):\n",
    "#                 if a!=b:\n",
    "#                     lis=[]\n",
    "#                     i=0\n",
    "#                     for key in range(len(s)):\n",
    "#                         if s[key] == c0:\n",
    "#                             lis.append(1)\n",
    "#                         elif s[key] == c1:\n",
    "#                             lis.append(-1)\n",
    "#                         else:\n",
    "#                             lis.append(0)\n",
    "#                         i = i + 1\n",
    "#                     if min(lis)>=0:\n",
    "#                         return 0\n",
    "#                     f=[0]\n",
    "#                     g=[-1000]\n",
    "#                     for i in range(1,len(lis)+1):\n",
    "#                         f.append(0)\n",
    "#                         g.append(0)\n",
    "#                         if lis[i-1]==1:\n",
    "#                             f[i]=max(0,f[i-1])+1\n",
    "#                             g[i]=g[i-1]+1\n",
    "#                         elif lis[i-1]==-1:\n",
    "#                             f[i]=max(0,f[i-1])-1\n",
    "#                             g[i]=max(f[i-1],0)-1\n",
    "#                         else:\n",
    "#                             f[i]=f[i-1]\n",
    "#                             g[i]=g[i-1]\n",
    "#                         ans=max(max(g),ans)\n",
    "#         return ans\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        pos = defaultdict(list)\n",
    "        for i, ch in enumerate(s):\n",
    "            pos[ch].append(i)\n",
    "        ans = 0\n",
    "        for c0, pos0 in pos.items():\n",
    "            for c1, pos1 in pos.items():\n",
    "                if c0 != c1:\n",
    "                    i = j = 0\n",
    "                    f, g = 0, float(\"-inf\")\n",
    "                    while i < len(pos0) or j < len(pos1):\n",
    "                        if j == len(pos1) or (i < len(pos0) and pos0[i] < pos1[j]):\n",
    "                            f, g = max(f, 0) + 1, g + 1\n",
    "                            i += 1\n",
    "                        else:\n",
    "                            f, g = max(f, 0) - 1, max(f, g, 0) - 1\n",
    "                            j += 1\n",
    "                        ans = max(ans, g)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestVariance(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        pos = defaultdict(list)\n",
    "        for i, ch in enumerate(s):\n",
    "            pos[ch].append(i)\n",
    "        for ch1, pos1 in pos.items():\n",
    "            for ch2, pos2 in pos.items():\n",
    "                if ch1 == ch2:\n",
    "                    continue\n",
    "                i = j = f = 0\n",
    "                g = -inf\n",
    "                while i < len(pos1) or j < len(pos2):\n",
    "                    if j >= len(pos2) or i < len(pos1) and pos1[i] < pos2[j]:\n",
    "                        f, g = max(f, 0) + 1, g + 1\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        f, g = max(0, f) - 1, max(0, f, g) - 1\n",
    "                        j += 1\n",
    "                    ans = max(ans, g)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
